"""
https://leetcode.cn/problems/number-of-islands/

200. 岛屿数量
已解答
中等
相关标签
相关企业
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

 

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

"""

from typing import List


class Solution:
    """
    本体思路之一，从grid[0][0]开始，向上下左右4个方向进行遍历。
    如果能够达到，则在记录盘中记录，直到所有方向都无法遍历。
    这时再在记录盘中未标记的新位置开始进行第二次遍历。
    直到所有位置都在记录盘中标识已走过。
    此时遍历的总次数，就是小岛的数量。
    """
    def numIslands(self, grid: List[List[str]]) -> int:
        height=len(grid)
        width=len(grid[0])
        records=[[0]*width for _ in range(height)]

        def go_next(target:List[int])->bool:
            trow=target[0]
            tcol=target[1]
            if trow<0 or trow>=height or tcol<0 or tcol>=width:
                return False
            if grid[trow][tcol]=='0':
                return False
            if records[trow][tcol]=='1':
                return False
            records[trow][tcol]='1'
            return True
        
        count=0
        for r in range(height):
            for c in range(width):
                if records[r][c]==0 and grid[r][c]=='1':
                    records[r][c]=1
                    count+=1
                    to_go=[[r,c]]
                    while len(to_go)>0:
                        [nr,nc]=to_go[0]
                        # print(to_go)
                        to_go.pop(0)
                        
                        if go_next([nr-1,nc]):
                            to_go.append([nr-1,nc])
                        if go_next([nr+1,nc]):
                            to_go.append([nr+1,nc])
                        if go_next([nr,nc-1]):
                            to_go.append([nr,nc-1])
                        if go_next([nr,nc+1]):
                            to_go.append([nr,nc+1])

        return count

if __name__=='__main__':
    grid = [["1"],["1"]]
    sol=Solution()
    res=sol.numIslands(grid)
    print(res)
    pass